Brief background, we are running Lync Basic 2013 w/o an on premise Lync server. All credentials are stored in Office365. We've been having this issue for about a week now. When the client attempts to sign on it gets stuck on the "Connecting to server" step. No error messages, just keeps trying to connect. Also, this is not affecting the entire office, only about 4 users. All have had Lync running fine, and claimed Lync had stopped working after MS Windows updates were installed on 7/11/13. Here is what I've tried. 

-Lync Repair
-Updates Installed
-Manual server connection 
-Full client uninstall/re-install - all traces of registry entries/credentials were deleted prior to re-install
-Deleted/Re-created Lync profile
-Attempted to login with known good credentials, same outcome.
-Successful login attempt through Office365
-Imported known good certificate
-Attempted login to Lync under different system profile, same outcome.
-DNS Flush/IP release/Renew
-Corrected system time
-Reviewed MOSDAL logs per kb2541980
-Confirmed port 443 is Listening, and am able to resolve sipdir
-Turned off all firewalls/AV's running on client's machine. 
-Attempted login from outside our network, same outcome.
-Installed Sign-in assistant, same outcome. 
-User can sign in via mobile app

I'm losing my mind here, does anyone have any suggestions? Any other troubleshooting tips I can try? I've contacted MS support, and so far everything they've suggested are all from the kb articles I've tried. 

Thanks in advance to anyone that can help. 

Hi,

The issue is more related to Lync online, you can also post a question on Office365 forum to get further information. Thank you for your understanding.